package cn.qyd.leecode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @author 邱运铎
 * @date 2024-04-16 11:34
 */
public class BadNodeInfect {
    private int removeIndex;
    private int finalBadNodes;
    private int minfinalBadNode;

    public static void main(String[] args) {
        BadNodeInfect badNodeInfect = new BadNodeInfect();
//        int[][] graph = {{1,1,0},{1,1,0},{0,0,1}};
//        int[] initial = new int[]{0,1};
        int[][] graph = {{1,0,0},{0,1,0},{0,0,1}};
        int[] initial = new int[]{0,2};
        int i = badNodeInfect.minMalwareSpread(graph, initial);
        System.out.println(i);
    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        int m = graph.length;
        int n = initial.length;

        removeIndex = initial[0];
        finalBadNodes = 0;
        minfinalBadNode = m;

        int[] badNode = new int[m];
        Arrays.fill(badNode, -1);
        Queue<Integer> queue = new ArrayDeque<>();
        /**
         * 从最初被恶意软件感染的节点集合中最小节点开始，
         * 计算移除该节点后最终感染节点的数量
         */
        for (int i = 0; i < n; i++) {
            finalBadNodes = 0;
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    continue;
                }
                badNode[initial[j]] = i;
                finalBadNodes++;
                queue.offer(initial[j]);
            }
            while (!queue.isEmpty()) {
                int curBadNode = queue.poll();
                for (int k = 0; k < m; k++) {
                    if (graph[curBadNode][k] == 1 && badNode[k] != i) {
                        System.out.println(Arrays.toString(badNode));
                        badNode[k] = i;
                        queue.offer(k);
                        finalBadNodes++;
                    }
                }
            }
            if (finalBadNodes < minfinalBadNode) {
                minfinalBadNode = finalBadNodes;
                removeIndex = i;
            }

        }

        return removeIndex;

    }
}
